package com.huawei.M01.iterator;

import java.util.Scanner;

/**
 * 01背包问题
 * 有n个苹果，他们有各自的体积和价值，现有给定容量v的背包，如何让背包里装入的苹果具有最大的价值总和
 * 首行输入两个整数，n，v代表n个苹果和体积为v的背包。之后每行输入a和b代表每个苹果的体积和价值
 *
 * @author 111
 */
public class Knapsacks {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

    }

    private static int getMaxValue(int n, int v, int[] weight, int[] value) {
        int[][] dp = new int[n + 10][v + 10];
        // 遍历查找最优解
        for (int i = 1; i <= weight.length; i++) {
            for (int j = 1; j <= v; j++) {
                // 如果第j个苹果的体积大于剩余体积，则在背包中放不进去剩余的苹果了
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
                }
            }
        }
        return dp[n - 1][v - 1];
    }
}
